/*
In computer science, a binary tree is a tree data structure 
in which each node has at most two child nodes, usually distinguished
as "left" and "right". Nodes with children are parent nodes, and child nodes 
may contain references to their parents. Outside the tree, there is often a
reference to the "root" node (the ancestor of all nodes), if it exists.
Any node in the data structure can be reached by starting at root node
and repeatedly following references to either the left or right child.
 * 
 */
 package benarytree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 *
 * @author Дмитрий
 */
public class BinaryTree {
    private HashMap<Integer, TreeNode> nodeTree = 
            new HashMap<Integer, TreeNode>();
    private int currId = 0;
    
    /**
     * Constructor create a binary tree
     * BinaryTree always must contains at least one element 
     * @param value is data in root node 
     */
    public BinaryTree(String value) {
        TreeNode treeNode = new TreeNode(currId, value);
        treeNode.setLevel(0);
        nodeTree.put(currId, treeNode);
        currId++;
    }
    
    /**
     * Insert element to the binary tree
     * @param rootId a  parent node for new node
     * @param direct a plase where we insert a new node (right or left)
     * @param value is data in new node 
     */
    public void addNode(int rootId, Direct direct, String value) { 
        TreeNode rootNode = nodeTree.get(rootId);
        
        if(rootNode == null) {
            throw new IndexOutOfBoundsException("There is no such key!!!");
        }
        
        TreeNode treeNode = new TreeNode(currId, value);
        treeNode.setLevel(rootNode.getLevel() + 1);
        
        if(direct == Direct.LEFT) {
            if(rootNode.getLeftChild() != -1) {
                int nextId = rootNode.getLeftChild();
                TreeNode nextNode = nodeTree.get(nextId);
                nextNode.setLevel(nextNode.getLevel() + 1);
                treeNode.setLeftChild(nextId);
            }
            rootNode.setLeftChild(currId);
            
        }
        else {
            if(rootNode.getRightChild() != -1) {
                 int nextId = rootNode.getRightChild();
                 TreeNode nextNode = nodeTree.get(nextId);
                 nextNode.setLevel(nextNode.getLevel() + 1);
                 treeNode.setRightChild(nextId);
            }
            rootNode.setRightChild(currId);
        }
        
        nodeTree.put(currId, treeNode);
        
        currId++;
    }
    
    /**
     * 
     * @return a height of binary tree
     */
     public int getHeight() {
         int maxLevel = 0;
         for(int key: nodeTree.keySet()) {
             int currLevel = nodeTree.get(key).getLevel();
            if (currLevel > maxLevel) {
                maxLevel = currLevel;
            }
         }
         return maxLevel + 1;
     }
     
     /**
      * 
      * @param key id node that we want to search
      * @return string presentation of node or throw 
      * IndexOutOfBoundsException if node was not found
      */
    public String getNode(int key) {
        StringBuilder sb = new StringBuilder();
        TreeNode node = nodeTree.get(key);
        
        if(node == null) {
            throw new IndexOutOfBoundsException("There is no such key!!!");
        }
        
        sb.append("LEVEL ");
        sb.append(node.getLevel());           
        sb.append("\n");
        sb.append(node.getData());
        sb.append("\n");
        sb.append(node.getId());
        sb.append("->");
        sb.append(node.getLeftChild());
        sb.append(", ");
        sb.append(node.getRightChild());
        sb.append("\n");
        return sb.toString();
    }
    
    /*
     *Show string presentation of binary tree:
     * At first I print ziro level(only root),
     * then I print  first level(only children of root) and so on.... 
     */
    @Override
    public String toString() {
        List<StringBuilder> list =  getListPresentation();
        StringBuilder sb = new StringBuilder();
        
        for (int idx = 0; idx < list.size(); idx++) {
            sb.append(list.get(idx));
        }

        return sb.toString();
    }
    
    /**
     * 
     * @return a list presentation of binary tree:
     * first element is a string presentation of first level
     * second element is a string presentation of second level
     * and so on...
     */
    private List<StringBuilder> getListPresentation() {
        List<StringBuilder> list = new ArrayList<StringBuilder>();
        for (int i = 0; i < getHeight(); i++) {
            list.add(new StringBuilder());
        }
        
        for(int key: nodeTree.keySet()) {
            TreeNode node = nodeTree.get(key);           
            int level = node.getLevel();
            String s = getNode(key);
            list.get(level).append(s);
        }
        
        return list;
    }
}
